package librairies.arborescence;

import librairies.arborescence.arbre.BinarbreAVL;
import librairies.arborescence.arbre.BinarbreDC;
import librairies.arborescence.interfaces.IBinarbre;
import librairies.exception.ArbreCyclique;
import librairies.exception.GreffeDeSousArbre;
import librairies.exception.SousArbreIncoherent;
import librairies.liste.interfaces.IListeE;
import librairies.liste.list.ListeDCE;

import org.junit.Test;

public class BinarbreAVLTest
{
	@Test
	public void testexecut() throws NullPointerException, ArbreCyclique, GreffeDeSousArbre, SousArbreIncoherent	//FIXME nok
	{
		IBinarbre<Integer> av1 = new BinarbreAVL<Integer>(4);
		System.out.println(av1);
		av1 = av1.addVal(3);
		System.out.println(av1);
		av1 = av1.addVal(1);
		System.out.println(av1);
		av1 = av1.addVal(6);
		System.out.println(av1);
		av1 = av1.addVal(7);
		System.out.println(av1);
		av1 = av1.addVal(5);
		System.out.println(av1);
		av1 = av1.addVal(2);
		System.out.println(av1);
		System.out.println("#############");
		IListeE<Integer> listInit = new ListeDCE<Integer>();
		listInit.add(2).add(3).add(4).add(5);
		IBinarbre<Integer> a1 = new BinarbreDC<Integer>(1).addAll(listInit);
		listInit = new ListeDCE<Integer>();
		listInit.add(4).add(3).add(2).add(1);
		IBinarbre<Integer> a2 = new BinarbreDC<Integer>(5).addAll(listInit);
		listInit = new ListeDCE<Integer>();
		listInit.add(5).add(15).add(12).add(8).add(9).add(4).add(2).add(10).add(5).add(12).add(10).add(16).add(14).add(11);
		IBinarbre<Integer> a3 = new BinarbreDC<Integer>(10).addAll(listInit);
		listInit = new ListeDCE<Integer>();
		listInit.add(2).add(3).add(4).add(5);
		av1 = new BinarbreAVL<Integer>(1).addAll(listInit);
		listInit = new ListeDCE<Integer>();
		listInit.add(4).add(3).add(2).add(1);
		IBinarbre<Integer> av2 = new BinarbreAVL<Integer>(5).addAll(listInit);
		listInit = new ListeDCE<Integer>();
		listInit.add(5).add(15).add(12).add(8).add(9).add(4).add(2).add(10).add(5).add(12).add(10).add(16).add(14).add(11);
		IBinarbre<Integer> av3 = new BinarbreAVL<Integer>(10).addAll(listInit); 
		System.out.println("***** Bin / BinAVL :\n"+a1+"***\n"+av1);
		System.out.println("***** Bin / BinAVL :\n"+a2+"***\n"+av2);
		System.out.println("***** Bin / BinAVL :\n"+a3+"***\n"+av3);
		listInit = new ListeDCE<Integer>();
		listInit.add(13).add(14).add(15).add(16).add(17).add(18).add(19).add(20).add(21).add(22).add(23).add(24);
		a3.addAll(listInit);	listInit = new ListeDCE<Integer>();
		listInit.add(13).add(14).add(15).add(16).add(17).add(18).add(19).add(20).add(21).add(22).add(23).add(24);
		av3 = av3.addAll(listInit);
		System.out.println("############# ON IMPRIME EN PLUS L'EQUILIBRAGE");
		BinarbreDC.printBalance=true;
		System.out.println("***** Bin / BinAVL :\n"+a3+"***\n"+av3);
		System.out.println("############# RETOUR AFFICHAGE NORMAL");
		BinarbreDC.printBalance=false;
		av3 = av3.cutVal(53);
		System.out.println("***** Retrait de 53 : \n"+av3);
		av3 = av3.cutVal(2);
		System.out.println("***** Retrait de 2 : \n"+av3);
		av3 = av3.cutVal(9);
		System.out.println("***** Retrait de 9 : \n"+av3);
		av3 = av3.cutVal(10);
		System.out.println("***** Retrait de 10 : \n"+av3);
		av3 = av3.cutVal(5);
		System.out.println("***** Retrait de 5 : \n"+av3);
		av3 = av3.cutVal(11);
		System.out.println("***** Retrait de 11 : \n"+av3);
		av3 = av3.cutVal(18);
		System.out.println("***** Retrait de 18 : \n"+av3);
		av3 = av3.cutVal(16);
		System.out.println("***** Retrait de 16 : \n"+av3);
		listInit = new ListeDCE<Integer>();
		listInit.add(19).add(20).add(21);
		av3 = av3.cutAll(listInit);
		System.out.println("***** Retrait de 19, 20, 21 : \n"+av3);
		listInit = new ListeDCE<Integer>();
		listInit.add(22).add(24);
		av3 = av3.cutAll(listInit);
		System.out.println("***** Retrait de 22, 24 : \n"+av3);
		listInit = new ListeDCE<Integer>();
		listInit.add(12).add(17);
		av3 = av3.cutAll(listInit);
		System.out.println("***** Retrait de 12, 17 : \n"+av3);
		listInit = new ListeDCE<Integer>();
		listInit.add(8).add(4).add(13);
		av3 = av3.cutAll(listInit);
		System.out.println("***** Retrait de 8, 4, 13 : \n"+av3);
		av3 = av3.cutVal(15);
		System.out.println("***** Retrait de 15 : \n"+av3);
		av3 = av3.cutVal(14);
		System.out.println("***** Retrait de 14 : \n"+av3);
		av3 = av3.cutVal(23);
		System.out.println("***** Retrait de 23 : \n"+av3);
		/*
			4
			
			4
			|
			3
			
			3  
			+-+
			1 4
			
			3    
			+-+  
			1 4  
			  +-+
			    6
			
			3    
			+-+  
			1 6  
			  +-+
			  4 7
			
			4    
			+-+  
			3 6  
			| +-+
			1 5 7
			
			4      
			+---+  
			2   6  
			+-+ +-+
			1 3 5 7
			
			#############
			***** Bin / BinAVL :
			1        
			+-+      
			  2      
			  +-+    
			    3    
			    +-+  
			      4  
			      +-+
			        5
			***
			2    
			+-+  
			1 4  
			  +-+
			  3 5
			 
			***** Bin / BinAVL :
			5
			|
			4
			|
			3
			|
			2
			|
			1
			***
			4    
			+---+
			2   5
			+-+  
			1 3  
			
			***** Bin / BinAVL :
			10            
			+-----+       
			5     15      
			+-+   +-----+ 
			4 8   12    16
			| +-+ +--+    
			2   9 11 14   
			***
			10            
			+-----+       
			8     15      
			+---+ +-----+ 
			4   9 12    16
			+-+   +--+    
			2 5   11 14   
			
			############# ON IMPRIME EN PLUS L'EQUILIBRAGE
			***** Bin / BinAVL :
			10(7)                                          
			+------------+                                 
			5(0)         15(6)                             
			+-----+      +------------+                    
			4(-1) 8(1)   12(1)        16(8)                
			|    +-+    +-----+      +-+                  
			2(0)   9(0) 11(0) 14(-1)   17(7)              
			                   |       +-+                
			                   13(0)     18(6)            
			                              +-+              
			                                19(5)          
			                                +-+            
			                                  20(4)        
			                                  +-+          
			                                    21(3)      
			                                    +-+        
			                                      22(2)    
			                                      +-+      
			                                        23(1)  
			                                        +-+    
			                                          24(0)
			***
			10(1)                                                     
			+--------------+                                          
			8(-1)          18(0)                                      
			+---------+    +-----------------------+                  
			4(0)      9(0) 14(0)                   22(0)              
			+----+         +-----------+           +-----------+      
			2(0) 5(0)      12(0)       16(0)       20(0)       23(1)  
			               +-----+     +-----+     +-----+     +-+    
			               11(0) 13(0) 15(0) 17(0) 19(0) 21(0)   24(0)
			
			############# RETOUR AFFICHAGE NORMAL
			***** Retrait de 53 : 
			10                          
			+-----+                     
			8     18                    
			+---+ +-----------+         
			4   9 14          22        
			+-+   +-----+     +-----+   
			2 5   12    16    20    23  
			      +--+  +--+  +--+  +-+ 
			      11 13 15 17 19 21   24
			
			***** Retrait de 2 : 
			10                          
			+-----+                     
			8     18                    
			+---+ +-----------+         
			4   9 14          22        
			+-+   +-----+     +-----+   
			  5   12    16    20    23  
			      +--+  +--+  +--+  +-+ 
			      11 13 15 17 19 21   24
			
			***** Retrait de 9 : 
			18                        
			+---------------+         
			10              22        
			+---+           +-----+   
			5   14          20    23  
			+-+ +-----+     +--+  +-+ 
			4 8 12    16    19 21   24
			    +--+  +--+            
			    11 13 15 17           
			
			***** Retrait de 10 : 
			18                      
			+-------------+         
			8             22        
			+-+           +-----+   
			5 14          20    23  
			| +-----+     +--+  +-+ 
			4 12    16    19 21   24
			  +--+  +--+            
			  11 13 15 17           
			
			***** Retrait de 5 : 
			18                      
			+-------------+         
			14            22        
			+-------+     +-----+   
			8       16    20    23  
			+-+     +--+  +--+  +-+ 
			4 12    15 17 19 21   24
			  +--+                  
			  11 13                 
			
			***** Retrait de 11 : 
			18                     
			+------------+         
			14           22        
			+------+     +-----+   
			8      16    20    23  
			+-+    +--+  +--+  +-+ 
			4 12   15 17 19 21   24
			  +-+                  
			    13                 
			
			***** Retrait de 18 : 
			17                  
			+---------+         
			14        22        
			+------+  +-----+   
			8      16 20    23  
			+-+    |  +--+  +-+ 
			4 12   15 19 21   24
			  +-+               
			    13              
			
			***** Retrait de 16 : 
			17                
			+-------+         
			12      22        
			+-+     +-----+   
			8 14    20    23  
			| +--+  +--+  +-+ 
			4 13 15 19 21   24
			
			***** Retrait de 19, 20, 21 : 
			17           
			+-------+    
			12      23   
			+-+     +--+ 
			8 14    22 24
			| +--+       
			4 13 15      
			
			***** Retrait de 22, 24 : 
			12        
			+-+       
			8 17      
			| +-----+ 
			4 14    23
			  +--+    
			  13 15   
			
			***** Retrait de 12, 17 : 
			14       
			+----+   
			8    15  
			+-+  +-+ 
			4 13   23
			
			***** Retrait de 8, 4, 13 : 
			15   
			+--+ 
			14 23
			
			***** Retrait de 15 : 
			14  
			+-+ 
			  23
			
			***** Retrait de 14 : 
			23
			
			***** Retrait de 23 : 
			null
		*/
	}
}
